package CommonAlgs.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author ChanZany
 * @Date 2021/5/17 19:49
 * @Version 1.0
 */
public class TwoNumSum {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        while (l1 != null) {
            list1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            list2.add(l2.val);
            l2 = l2.next;
        }
        //补零
        int n = Math.max(list1.size(), list2.size());
        if (list1.size() > list2.size()) {
            int lowsize = list2.size();
            for (int i = 0; i < n - lowsize; i++) {
                list2.add(0);
            }
        } else {
            int lowsize = list1.size();
            for (int i = 0; i < n - lowsize; i++) {
                list1.add(0);
            }
        }

        int[] a = new int[n + 1];
        for (int i = 0; i < list1.size(); i++) {
            a[i] = list1.get(i) + list2.get(i);
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 0; i < list1.size(); i++) {
            if (a[i] >= 10) {
                a[i + 1] = a[i + 1] + 1;
                a[i] = a[i] - 10;
            }
            ListNode tmp = new ListNode(a[i]);
            p.next = tmp;
            p = tmp;
        }
        if (a[n] == 1) {
            p.next = new ListNode(a[n]);
        }

        return head.next;
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;//设置头尾哑节点
        int carry = 0;
        while (l1 != null || l2 != null) {
            //补零
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int sum = v1 + v2 + carry;
            if (head == null) { //第一次遍历时，将head节点和tail节点初始化为sum/10
                head = tail = new ListNode(sum % 10);
            } else { //2~n iteration, move tail and build the linkedList
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1!=null) l1 = l1.next;
            if (l2!=null) l2 = l2.next;
        }
        if (carry>0) tail.next = new ListNode(carry);
        return head;
    }

    public static void main(String[] args) {
        ListNode h1 = new ListNode(9);
        h1.next = new ListNode(9);
        h1.next.next = new ListNode(9);
        h1.next.next.next = new ListNode(9);
        h1.next.next.next.next = new ListNode(9);
        h1.next.next.next.next.next = new ListNode(9);
        ListNode h2 = new ListNode(9);
        h2.next = new ListNode(9);
        h2.next.next = new ListNode(9);
        addTwoNumbers(h1, h2);
    }

}
